#include <stdio.h>
#include <stdlib.h>

// 头节点，首节点，尾节点概念 见p33 图2-9 带头节点的单链表示意图。
typedef int elementype;
typedef struct node
{
    elementype data;
    struct node *next;
} LinkList;

int After_LinkList();

// 图2-10 头插法建立单链表示意图 p34
LinkList *Create_LinkListF(int *arr, int length)
{
    // 创建一个头节点
    LinkList *head;
    head = (LinkList *)malloc(sizeof(LinkList));
    head->next = NULL;

    if (arr != NULL && length != 0)
    {
        for (size_t i = 0; i < length; i++)
        {
            LinkList *p = (LinkList *)malloc(sizeof(LinkList));
            p->data = arr[i];
            After_LinkList(head, p);
        }
        return head;
    }

    return head;
}

// 后插法
int After_LinkList(LinkList *head, LinkList *p)
{
    p->next = head->next;
    head->next = p;
    return 1;
}

// 打印链表
int Print_LinkList(LinkList *head)
{
    for (LinkList *p = head->next; p != NULL; p = p->next)
    {
        printf("%3d", p->data);
    }
    putchar('\n');
}

// 求单链表的长度
int LinkList_Length(LinkList *head)
{
    LinkList *p = head;
    int j = 0;
    while (p->next != NULL)
    {
        p = p->next; // p 指的是第j个节点
        j++;
    }
    return j;
}

// 单链表的查找
LinkList *GetData_LinkList(LinkList *head, int i)
{

    // 校验位置参数有效性
    if (i < 1)
    {
        return NULL;
    }

    int j = 1;
    LinkList *p;
    for (p = head->next; p != NULL && j < i;)
    {
        p = p->next;
        j++;
    }
    return p;
}

// 单链表后插
int InsertAfter_LinkList(LinkList *p, LinkList *s)
{
    s->next = p->next;
    p->next = s;
}

// 单链表的指定位置插入
int InsertNo_LinkList(LinkList *head, LinkList *s, int i)
{

    // 校验位置参数有效性
    if (i <= 0)
    {
        return 0;
    }

    LinkList *p = GetData_LinkList(head, i - 1); // 获取前驱节点
    InsertAfter_LinkList(p, s);
    return 1;
}

// 单链表删除后继节点
int DeleteAfter_LinkList(LinkList *p)
{
    if (p == NULL)
    {
        return 0;
    }

    LinkList *r = p->next; // p的后继节点
    if (r == NULL)
    {
        return 0;
    }
    p->next = r->next; // 修改p的后继节点

    r->data = 0;
    r->next = NULL;
    free(r);
    return 1;
}

int DeleteNo_LinkList(LinkList *head, int i)
{
    LinkList *p = GetData_LinkList(head, i - 1); // 前置节点
    DeleteAfter_LinkList(p);
    return 1;
}

// 单链表的置空
LinkList *SetNull_LinkList(LinkList *head)
{
    LinkList *p = head;
    while (p->next != NULL)
    {
        DeleteAfter_LinkList(p);
    }
    return p;
}

int main()
{
    // 循环头插法创建节点
    int arr[] = {11, 78, 23, 53, 74};
    int length = sizeof(arr) / sizeof(arr[0]);
    LinkList *l = Create_LinkListF(arr, length);
    printf("测试头插法创建节点:");
    Print_LinkList(l);
    putchar('\n');

    // 手动创建一个新的节点
    LinkList *p = (LinkList *)malloc(sizeof(LinkList));
    p->data = 96;
    p->next = NULL;

    LinkList *t = GetData_LinkList(l, 3);
    printf("测试查找指定位置:%d\n", t->data);
    // 测试插入指定位置节点函数
    int position = 3;
    InsertNo_LinkList(l, p, position);
    printf("测试插入指定位置节点:");
    Print_LinkList(l);
    putchar('\n');

    // 测试删除指定位置节点函数
    DeleteNo_LinkList(l, position);
    printf("测试删除指定位置节点:");
    Print_LinkList(l);
    putchar('\n');

    return 0;
}